package sort

//import "fmt"

//这个版本的时间复杂度比较高不建议用
type HeapSortV2 struct {
}

func NewHeapSortV2() *HeapSortV2 {
	return &HeapSortV2{}
}

func (h *HeapSortV2) Sort(nums []int) []int {
	l := len(nums) - 1
	for i := l/2 - 1; i >= 0; i-- {
		h.adjustHeap(nums, i, l)
	}

	for i := l; i > 0; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		l--
		h.adjustHeap(nums, 0, l)
	}
	return nums
}

func (h *HeapSortV2) adjustHeap(nums []int, i, l int) {
	maxIdx := i
	rightIdx, leftIdx := i*2+2, i*2+1
	//检查右子树
	if rightIdx < l && nums[rightIdx] > nums[maxIdx] {
		maxIdx = rightIdx
	}

	//检查左子树
	if leftIdx < l && nums[leftIdx] > nums[maxIdx] {
		maxIdx = leftIdx
	}

	if maxIdx != i {
		nums[maxIdx], nums[i] = nums[i], nums[maxIdx]
		h.adjustHeap(nums, maxIdx, l)
	}
}
